class Solution {
    public:
        int minCut(string s) {
            int n = s.size();
            vector<vector<bool>> is_recur(n,vector<bool>(n));
            for(int i = n-1 ; i >= 0 ; i--){
                for(int j = i ;  j < n ; j++){
                    if(s[i] == s[j]){
                        is_recur[i][j] = i+1 < j ? is_recur[i+1][j-1]:true;
                    }
                }
            }
            vector<int> dp(n); //以i位置为结尾的串至少需要多少刀
            dp[0] = 0;
            for(int i = 1 ; i < n ; i++){
                if(is_recur[0][i]) dp[i] = 0;
                else{
                    int mindp = INT_MAX;
                    for(int j = i ; j > 0 ;j--){
                        if(is_recur[j][i]){
                            mindp = min(mindp,dp[j]);
                        }
                    }
                    dp[i] = mindp+1;
                }
            }
            return dp[n-1];
        }
    };